function fib1(n: number): number {
  if (n < 2) return n;
  return fib1(n - 1) + fib(n - 2);
}

// 动态规划思想
function fib(n: number): number {
  // 小于2 直接返回
  if (n < 2) return n;
  // 初始化数组
  const result = new Array(0);
  // 赋初始值
  result[0] = 0;
  result[1] = 1;
  // console.log(result.length);
  // 循环从2开始到n结束 每次循环push前两位的和
  for (let i = 2; i < n + 1; i++) {
    result.push(result[i - 1] + result[i - 2]);
  }
  // 最后数组的第n项就是答案
  return result[n];
}
console.log(fib(4));
